# n 位格雷码序列 是一个由 2ⁿ 个整数组成的序列，其中：
#  每个整数都在范围 [0, 2ⁿ - 1] 内（含 0 和 2ⁿ - 1）
#  第一个整数是 0
#  一个整数在序列中出现 不超过一次
#  每对 相邻 整数的二进制表示 恰好一位不同 ，且
#  第一个 和 最后一个 整数的二进制表示 恰好一位不同
#  给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
#
#  示例 1：
# 输入：n = 2
# 输出：[0,1,3,2]
# 解释：
# [0,1,3,2] 的二进制表示是 [00,01,11,10] 。
# - 00 和 01 有一位不同
# - 01 和 11 有一位不同
# - 11 和 10 有一位不同
# - 10 和 00 有一位不同
# [0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
# - 00 和 10 有一位不同
# - 10 和 11 有一位不同
# - 11 和 01 有一位不同
# - 01 和 00 有一位不同
#
#  示例 2：
# 输入：n = 1
# 输出：[0,1]
from typing import List


class Solution:
    def grayCode2(self, n: int) -> List[int]:
        """
        解法二：公式法
        先右移一位，再做异或 连续的数字正好只有一位二进制不同
        :param n:
        :return:
        """
        return [((i >> 1) ^ i) for i in range(1 << n)]  # 将i向后移动一位，再和i取异或，相当于和自己的后一位取余

    def grayCode1(self, n: int) -> List[int]:
        """
        动态规划(由前面的结果迭代得到后面的结果)
        一位格雷码只有两个元素，[1， 0]
        格雷码 n 每增加1，包含的数字会翻倍，
            即：当n位格雷码包含c个数，则 n+1 位格雷码包含数字的个数 m, m = 2c
        满足以下规律：
        (n + 1)位格雷码中的前c个数是 n 位格雷码的所有数字前面补0，就相当于全部都是 n 中的全部数字
        而 (n+1) 中的后c个数是n中的所有数字前面补1，然后变为逆序

        以n = 2为例:
        n = 2 格雷码为 [00,  01,  11,  10]
        那么 n=3 的格雷码为[000, 001, 011, 010,| 110, 111, 101, 100](以|切成两部分)
            前半部分：
                就是分别在 n=2的每个格雷码最高位加上0，即得到[000, 001, 011, 010]
            后半部分：
                先分别在 n=2的每个格雷码最高位加上1，即得到[100, 101, 111, 110](前四个)，
                再将其变为逆序，即得到[110, 111, 101, 100](后四个)
        两部分拼接在一起即得到最后的结果[000, 001, 011, 010,| 110, 111, 101, 100]
        :param n:
        :return:
        """
        res = [0]
        for i in range(1, n + 1):
            for j in range(len(res) - 1, -1, -1):
                res.append(res[j] | (1 << (i - 1)))
        return res

    def grayCode(self, n: int) -> List[int]:
        return self.grayCode1(n)


if __name__ == "__main__":
    n = 3
    print(Solution().grayCode(n))
